package leetCode;

public class LeetCode_day2 {

	/**
	 * Find the longest palindromic substring in S
	 * Assume the longest length of s is 1000
	 * and there exist one unique longest palindromic substring.
	 * 
	 * Dynamic Programming Solution O(n^2), O(n^2) space
	 * 
	 * Define P[i,j] is true iff s[i,i] is a palindromic string
	 * Base:  P[i,i] is true
	 * 		  P[i,i+1] is true iff s[i] == s[i+1]
	 * Induction: 
	 * 		  P[i,j] is true iff P[i+1, j-1] is true && s[i] == s[j]
	 * 
	 * @param s
	 * @return
	 */
	public static String longestPalindromicSubstring(String s){
		if(s == null || s.isEmpty()) return null;
		if(s.length() == 1) return s;
		boolean[][] p = new boolean[s.length()][s.length()];
		int maxLen = 1, start = 0;
		//load base case
		for(int i = 0 ; i < s.length() ; i++) p[i][i] = true;
		for(int i = 0 ; i < s.length()-1 ; i++)
			if(s.charAt(i) == s.charAt(i+1)){
				p[i][i+1] = true;
				maxLen = 2;
				start = i;
			}
		//find all palindromic substring with length which >= 3
		//why 3? because when maxLen == 1, and no p[i][i+1] == true
		//then the next possible length is 3
		for(int len = 3; len <= s.length() ; len++){
			//start character begins from 0 to s.length()-len+1
			//notice, not s.length()-len because we should cover all conditions
			for(int i = 0 ; i < s.length()-len+1 ; i++){
				int j = i+len-1; 
				if(p[i+1][j-1] == true && s.charAt(i) == s.charAt(j)){
					p[i][j] = true;
					if(maxLen < len){
						maxLen = len;
						start = i;
					}
				}
			}
		}
		
		return s.substring(start, start+maxLen);
	}
	
	
	/**
	 * Dynamic Programming-----Expand Center
	 * O(n^n) O(n) space
	 * @param s
	 * @return
	 */
	public static String longestPalindromicSubstring1(String s){
		if(s == null || s.isEmpty()) return null;
		if(s.length() == 1) return s;
		String result = s.substring(0,1);
		
		for(int i = 0 ; i < s.length()-1 ; i++){
			//when the center is one character
			String temp = expandCenter(s,i,i+1);
			if(temp.length() > result.length()) result = temp;
			//when the center is two character
			if(s.charAt(i) == s.charAt(i+1)) {
				temp = expandCenter(s,i,i+2);
				if(temp.length() > result.length()) result = temp;
			}
		}
		return result;
	}
	
	public static String expandCenter(String s, int l, int r){
		while(r<s.length() && l > 0 && s.charAt(l) == s.charAt(r-1)){
			r++; l--;
		}
		return s.substring(l, r);
	}
	
	/**
	 * Manacher’s algorithm O(n)
	 * @param s
	 * @return
	 */
	//TODO
	public static String longestPalindromicSubstring2(String s){
		if(s == null || s.isEmpty()) return null;
		
		
		return null;
	}
	
	/**
	 * Using Suffix Tree O(n)
	 * @param s
	 * @return
	 */
	public static String longestPalindromicSubstring3(String s){
		if(s == null || s.isEmpty()) return null;
		
		
		return null;
	}
	
	/**
	 * Writing in a zigzag pattern on a given number of rows.
	 * All needed to do is simply counting.
	 * 
	 * Need a clear train of thought.
	 * 
	 * Separately deal with each row
	 * 
	 * @param s
	 * @param nRows
	 * @return
	 */
	public static String zigzagConversition(String s, int nRows){
		if(s.length() <= nRows) return s;
		char[] result = new char[s.length()];
		int blockSize = nRows * 2 - 2;
		int blockNum = s.length() / blockSize;
		int interval = (nRows-1) * 2;
		int ind = 0 , residual = 0;

		//for the first row, every block contains only one character with a constant interval
		for(int i = 0 ; i < blockNum ; i++){
			result[ind++] = s.charAt(interval * i);
		}
		//check residuals
		residual = interval * blockNum;
		if(residual < s.length()) result[ind++] = s.charAt(residual);
		
		//for rows in the middle, every block has two characters with a constant interval
		for(int i = 1 ; i < nRows - 1 ; i++){
			int newInterval = interval - 2 * i;
			for(int j = 0 ; j < blockNum ; j++){//for every block
				int first = i + j * interval;
				result[ind++] = s.charAt(first);//for the first character
				result[ind++] = s.charAt(first + newInterval);//for the second character
			}
			//check residuals
			//for the first character
			residual = i + blockNum * interval;
			if(residual < s.length()) result[ind++] = s.charAt(residual);
			//for the second character
			residual = residual + newInterval;
			if(residual < s.length()) result[ind++] = s.charAt(residual);
		}
		
		//for the last row, every block contains only one character with a constant interval
		for(int i = 0 ; i < blockNum ; i++){
			result[ind++] = s.charAt(nRows - 1 + interval * i);
		}
		//check residuals
		residual = interval * blockNum + nRows - 1;
		if(residual < s.length()) result[ind++] = s.charAt(residual);
		
		return new String(result);
	}
	/**
	 * Optimization 2ed
	 * @param s
	 * @param nRows
	 * @return
	 */
	public static String zigzagConversition1(String s, int nRows){
		if(s.length() <= nRows) return s;
		char[] result = new char[s.length()];
		int ind = 0, interval = (nRows-1)*2;
		for(int i = 0 ; i < nRows ; i++){//for every row
			//for every block
			for(int start = i ; start < s.length() ; start+= interval){
				result[ind++] = s.charAt(start);//add red element
				//add middle element
				if(i == 0 || i == nRows - 1) continue;
				int second = start+interval-2*i;
				if(second < s.length()) result[ind++] = s.charAt(second);
			}
		}
		return new String(result);
	}
	
	/**
	 * Code from Internet
	 * http://fisherlei.blogspot.com/2013/01/leetcode-zigzag-conversion.html
	 * @param s
	 * @param nRows
	 * @return
	 */
	
	public static String zigzagConversition3(String s, int nRows){
		if(s.length() <= nRows) return s;
		char[] result = new char[s.length()];
		int ind = 0;
		for(int i = 0 ; i < nRows ; i++){//for every row
			for(int j = 0, index = i ; 
					index < s.length(); j++, index = (2*nRows-2)*j+i){
				result[ind++] = s.charAt(index);//red element
				if(i == 0 || i == nRows - 1) continue;//middle element in the block
				if(index+(nRows-i-1)*2<s.length()) result[ind++] = s.charAt(index+(nRows-i-1)*2);
			}
		}
		
		return new String(result);
	}
	
	/**
	 * Reverse digits of an integer.
	 * 
	 * from high digits to low digits of a
	 * 
	 * 1) for integers like: 0 , 10, 100, how to reverse?
	 * 2) there are possibility of overflow, ex: 
	 * 			reverse of 1000000003 overflows
	 * @param a
	 * @return
	 */
	public static int reverseInteger(int a){
		int result=0, digitNum = 0;
		while(a % Math.pow(10, digitNum++) != a);
		int totalNum = --digitNum;
		result = a / (int)Math.pow(10,--digitNum);
		while(digitNum > 0){
			int nextDigit = (a - a/(int)Math.pow(10, digitNum)*(int)Math.pow(10, digitNum) - a%(int)Math.pow(10, digitNum-1))/(int)Math.pow(10, digitNum-1);
			result += nextDigit * Math.pow(10, totalNum-digitNum);
			digitNum--;
		}
		return result;
	}
	
	/**
	 * 2ed
	 * from low digits to high digits of a
	 * @param a
	 * @return
	 */
	public static int reverseInteger2(int a){
		int result=0;
		while(a != 0){
			result = result * 10 + a % 10;
			a /= 10;
		}
		return result;
	}
	
	/**
	 * Convert a string to an integer
	 * What if the string is negative?
	 * What if the string is not valid?
	 *
	 * No checkout on overflow
	 * @param s
	 * @return
	 */
	public static Integer atoi(String s) throws Exception{
		if(s == null || s.isEmpty()) throw new Exception("invlid input");
		boolean isValid = s.matches("^(-)?\\d+");
		if(!isValid) throw new Exception("invalid input");
		//check whether negative
		boolean isNagative = s.charAt(0) == '-';
		int result = 0;
		
		if(isNagative){
			for(int i = s.length()-1 ; i >= 1 ; i--){
				result += Character.getNumericValue(s.charAt(i)) * Math.pow(10, s.length()-i-1);
			}
			result = -result;
		}else{
			for(int i = s.length()-1 ; i >= 0 ; i--){
				result += Character.getNumericValue(s.charAt(i)) * Math.pow(10, s.length()-i-1);
			}
		}
		return result;
	}
	
	/**
	 * Convert a string to an integer
	 * What if the string is negative?
	 * What if the string is not valid?
	 *
	 * Have checkout on overflow
	 * @param s
	 * @return
	 */
	public static Integer atoi1(String s) throws Exception{
		if(s == null || s.isEmpty()) throw new Exception("invlid input");
		boolean isValid = s.matches("^(-)?\\d+");
		if(!isValid) throw new Exception("invalid input");
		//check whether negative
		boolean isNagative = s.charAt(0) == '-';
		int result = 0;
		int limit = Integer.MAX_VALUE / 10;//equals -Integer.MIN_VALUE / 10;
		int plastDigit = Integer.MAX_VALUE % 10;
		int nlastDigit = -(Integer.MIN_VALUE % 10);
		//notice: -Integer.MIN_VALUE is wrong, because you cannot calculate -Integer.MIN_VALUE = Integer.MIN_VALUE;
		
		if(isNagative){
			if(s.length() > 11) throw new Exception("invlid input");
			for(int i = 1 ; i < s.length() ; i++){
				result = result * 10 + Character.getNumericValue(s.charAt(i));
				if(result > limit && s.length() == 11) throw new Exception("invlid input");
				else if(result == limit && Character.getNumericValue(s.charAt(s.length()-1)) > nlastDigit)
					throw new Exception("invlid input");
			}
			result = -result;
		}else{
			if(s.length() > 10) throw new Exception("invlid input");
			for(int i = 1 ; i < s.length() ; i++){
				result = result * 10 + Character.getNumericValue(s.charAt(i));
				if(result > limit && s.length() == 10) throw new Exception("invlid input");
				else if(result == limit && Character.getNumericValue(s.charAt(s.length()-1)) > plastDigit)
					throw new Exception("invlid input");
			}
		}
		return result;
	}
	
	/**
	 * Determine whether an integer is a palindrome. 
	 * Do this without extra space.
	 * @param a
	 * @return
	 */
	public static boolean palindromeNumber(int a){
		if(a < 0) return false;
		String s = String.valueOf(a);
		int start = 0 , end = s.length() - 1;
		while(start < end){
			if(s.charAt(start) != s.charAt(end)) return false;
			start++;
			end--;
		}
		return true;
	}
	
	/**
	 * Determine whether an integer is a palindrome. 
	 * Do this without extra space.
	 * 
	 * for a = 4321
	 * 4 = 4321 / 1000 % 10
	 * 3 = 4321 / 100 % 10
	 * @param a
	 * @return
	 */
	public static boolean palindromeNumber1(int a){
		if(a < 0) return false;
		int digitNum = 0;
		while((a / (int) Math.pow(10, digitNum++)) != 0);
		digitNum--;
		int half = digitNum / 2;
		for(int i = 0 ; i < half ; i++){
			short low = (short) (a /(int)Math.pow(10, i) % 10);
			short high = (short)(a /(int)Math.pow(10, digitNum-i-1) % 10);
			if(low != high) return false;
		}
		return true;
	}
	
	/**
	 * Determine whether an integer is a palindrome. 
	 * Do this without extra space.
	 * Code From Internet
	 * 12321
	 * div = 10000
	 * l = 1 = r = 1: two sides of the number
	 * 12321 % div = 2321
	 * 2321 / 10 = 232: turn 12321 into 232
	 * div = 100
	 * @param a
	 * @return
	 */
	public static boolean palindromeNumber2(int a){
		if(a < 0) return false;
		int div = 1;
		while(a / div >= 10) div *= 10;
		while(a != 0){
			int l = a / div;
			int r = a % 10;
			if(l != r) return false;
			a = (a % div) / 10;
			div /= 100;
		}
		return true;
	}
	
	/**
	 * Determine whether an integer is a palindrome. 
	 * Do this without extra space.
	 * Code From Internet
	 * reverse a to get a' and check whether a == a'
	 * @param a
	 * @return
	 */
	public static boolean palindromeNumber3(int a){
		int x = a;
		int y = 0 ;
		for( ; a > 0 ; a = a / 10) //reverse this integer
			y = y*10 + a%10;
		return (x == y);
	}
	
	/**
	 * Implement regular expression matching with support for '.' and '*'.
	 * '.' Matches any single character.
	 * '*' Matches zero or more of the preceding element.
	 * @param s
	 * @param p
	 * @return
	 */
	//TODO need improvement
	public static boolean regularExpressionMatching(String ss, String ee){
		char[] s = ss.toCharArray();
		char[] e = ee.toCharArray();
		int ind = 0;
		for(int i = 0 ; i < e.length ; i++){
			if(s[ind] == e[i]){
				ind++;
				continue;
			}else if(e[i] == '*'){
				if(s[ind] == e[i-1]){//'aa' and 'a*'
					ind++;
					i--;//stay in this state
					continue;
				}
				if(e[i-1] == '.'){//'ab' and '.*' or 'ab' and '.*'
					if(e[i+1] != s[ind]) {
						ind++;
						i--;//stay in this state
					}  
					continue;
				}
				if(e[i+1] == s[ind]){
					ind++;
					i++;//go to next state
					continue;
				}			
			}else if(e[i] == '.'){
				ind++;
				continue;
			}else if(e[i+1] == '*'){
				i++;//next state
				continue;
			}
			return false;
		}
		return true;
	}
	
	public static void main(String[] args) {
		System.out.println(longestPalindromicSubstring1("fgabcbaedabcddcba"));
		System.out.println(zigzagConversition1("PAYPALISHIRING", 3));
		System.out.println(reverseInteger(432123432));
		try {
			System.out.println(atoi1("-2147483648"));
		} catch (Exception e) {
			e.printStackTrace();
		}
		System.out.println(regularExpressionMatching("aab", "c*d*a*b"));
		System.out.println(palindromeNumber3(12341));
	}

}
/**
 * Notice:
 * char[] a = new char[3]{a};
 * a.toString() will give the string of the serialized object;
 * new String(a) will give the "aaa";
 * 
 * range of integer: 32-bits 
 * 					 (-2147483648, 2147483647) 10-digits
 * 					 (-2^31-1, 2^31)
 * 
 * Several methods to check whether a String is contained by only digits
 * 1)	mat = s.matches("\\d+");
 * 2)	Character.isDigit(s.charAt(i))
 * 3)	int chr = s.charAt(i); chr < 48 || chr > 57, return false
 * 
 * convert character to integer:
 * 		Character.getNumericValue(c);
 * 
 * -Integer.MIN_VALUE = Integer.MIN_VALUE
 * -Integer.MIN_VALUE % 10 = -8
 * -(Integer.MIN_VALUE % 10) = 8
 * */
